/* 

给定一个仅包含 0 和 1 、大小为 rows x cols 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。

示例 1：
输入：matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
输出：6
解释：最大矩形如上图所示。

示例 2：
输入：matrix = []
输出：0

示例 3：
输入：matrix = [["0"]]
输出：0

示例 4：
输入：matrix = [["1"]]
输出：1

示例 5：
输入：matrix = [["0","0"]]
输出：0
 

提示：
rows == matrix.length
cols == matrix[0].length
0 <= row, cols <= 200
matrix[i][j] 为 '0' 或 '1'

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/maximal-rectangle
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

*/

// 题解：https://leetcode-cn.com/problems/maximal-rectangle/solution/85-zui-da-ju-xing-by-alexer-660/
// 思路参考“84 柱状图中最大的矩形”

/**
 * @param {character[][]} matrix
 * @return {number}
 */
// 栈解
// 单调栈
var maximalRectangle = function (matrix) {
    if (!matrix || matrix.length == 0) {
        return 0;
    }

    // 和 84.柱状图中最大的矩形 一样的方法
    const largestRectangleArea = function (heights) {
        const stack = [];
        heights = [0, ...heights, 0];

        for (let i = 0; i < heights.length; i++) {
            while (heights[i] < heights[stack[stack.length - 1]]) { // 当前bar比栈顶bar矮
                const tempIndex = stack.pop(); // 栈顶元素出栈，并保存栈顶bar的索引
                const height = heights[tempIndex];
                const width = i - 1 - stack[stack.length - 1];
                maxarea = Math.max(maxarea, height * width); // 计算面积，并挑战最大面积
            }
            stack.push(i); // 当前bar比栈顶bar高了，入栈
        }
    }

    const row = matrix.length;
    const col = matrix[0].length;
    const heights = new Array(col).fill(0);
    let maxarea = 0;

    for (let i = 0; i < row; i++) {
        for (let j = 0; j < col; j++) {
            if (matrix[i][j] == '1') {
                heights[j] += 1;
            } else {
                heights[j] = 0;
            }
        }
        largestRectangleArea(heights);
    }
    return maxarea;
}